Previous | Index | Next |

Structure of the library

The library contains five main kinds of components: Such decomposition allows us to dramatically reduce the component space. For example, instead of providing a search member function for every kind of container we provide a single version that works with all of them as long as a basic set of requirements is satisfied. The following description helps clarify the structure of the library. If software components are tabulated as a three-dimensional array, where one dimension represents different data types (e.g. int, double), the second dimension represents different containers (e.g. vector, linked-list, file), and the third dimension represents different algorithms on the containers (e.g. searching, sorting, rotation), if i, j, and k are the size of the dimensions, then i*j*k different versions of code have to be designed. By using function object that encapsulate the difference between the data types, we need only j*k versions. Further, by making our algorithms work on different containers, we need merely j+k versions. This significantly simplifies software design work and also makes it possible to use components in the library together with user defined components in a very flexible way.
A user may easily define a specialized container class and use the library's sort function to sort it. A user may provide a different comparison function for the sort as a function object (an object with a compare() method defined) that does the comparisons. If a user needs to iterate through a container in the reverse direction, the ReverseIterator adaptor allows that.

The library extends the basic Java paradigms in a consistent way, so it is easy for a Java programmer to start using the library. For example, the library contains a merge algorithm function. When a user has two arrays a and b to be merged into c it can be done with:

    Object a[] = new Object[100];
    Object b[] = new Object[200];
    Object c[] = new Object[300];
    ...
    merge(Array.begin(a), Array.end(a), Array.begin(b), Array.end(b), Array.begin(c));
When a user wants to merge a vector and a list (both of which are classes in the library) and put the result into a set it can be done with
    Vector a;
    List b;
    Set c;
    ...
    merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
where begin() and end() are member functions of containers that return the right types of iterators or pointer-like objects that allow the merge to do the job. In many cases it is useful to iterate through input/output streams in the same way as through regular data structures. For example, if we want to merge two data structures and then store them in a file, it would be nice to avoid creation of an auxiliary data structure for the result, instead storing the result directly into the corresponding file. The library provides both InputStreamIterator and OutputStreamIterator classes to make many of the library algorithms work with I/O streams that represent homogenous aggregates of data. Here is a program that reads a file of integers from the standard input, removes all those that are divisible by its command argument, and writes the result to the standard output:
    package sjlExample;
    import sjl.*;
    import sjl.wrappers.*;
    
    class Modulus0 implements Predicate1 {
        Function2 modulus;
        Object value;
        public Modulus0(Object val) {
	    value = val;
 	    modulus = new FuncModulusInteger();
        }
        public boolean compare(Object o) {
	    return ((Integer)modulus.perform(o, value)).intValue() == 0;
        }
    }
    
    public class Exam01 {
        public static void main(String argv[]) {
            if (argv.length != 1) {
	        System.err.println("usage: Exam01 integer");
	        System.exit(1);
	    }
            Algo.remove_copy(new InputStreamIterator(System.in, 
		    new FuncTextReaderInteger()),
                    new InputStreamIterator(),
                    new OutputStreamIterator(System.out, new FuncTextWriter(), " "),
		    new Modulus0(Integer.valueOf(argv[0])));
	    System.out.println("");
        }
    }

Source here.
All the work is done by remove_copy which reads integers one by one until the input iterator becomes equal to the end-of-stream iterator that is constructed by the constructor with no arguments. (In general, all the algorithms work in a "from here to there" fashion taking two iterators that signify the beginning and the end of the input.) Then remove_copy writes the integers that pass the test onto the output stream through the output iterator that is bound to System.out. As a predicate, remove_copy uses a function object constructed from a function object, ModulusInt, which takes i and j and returns i%j, as a binary predicate and makes it into a unary predicate by using Bind2nd to bind the second argument to the command line argument, atoi(argv[1]). Then the negation of this unary predicate is obtained using function adaptor Not1.

A somewhat more realistic example is a filter program that takes a file and randomly shuffles its lines.

    static void main(String argv[]) {
        if (argv.length != 1)
	    throw("usage: shuffle\\n");
        Vector v = new Vector();
        Algo.copy(new InputStreamIterator(System.in, new FuncReaderString()), 
             new InputStreamIterator(),
             new InsertIterator(v, v.end()));
        Algo.random_shuffle(v.begin(), v.end());
        Algo.copy(v.begin(), v.end(), 
             new OutputStreamIterator(System.out, new FuncTextWriter(), "\n"));
    }
In this example, copy moves lines from the standard input into a vector, but since the vector is not preallocated it uses an insert iterator to insert the lines one by one into the vector. (This technique allows all of the copying functions to work in the usual overwrite mode as well as in the insert mode.) Then random_shuffle shuffles the vector and another call to copy copies it onto the System.out stream.


Previous | Index | Next |